%% Rutas aéreas predefinidas.

% llega(?origen, ?destino, ?tiempo)
llega(buenos_aires, mdq, 1).
llega(buenos_aires, cordoba, 2).
llega(buenos_aires, rio, 4).
llega(buenos_aires, madrid, 12).
llega(buenos_aires, atlanta, 11).
llega(mdq, buenos_aires, 1).
llega(cordoba, salta, 1).
llega(salta, buenos_aires, 2).
llega(rio, buenos_aires, 4).
llega(rio, new_york, 10).
llega(atlanta, new_york, 3).
llega(new_york, madrid, 9).
llega(madrid, lisboa, 1).
llega(madrid, buenos_aires, 12).
llega(lisboa, madrid, 1).
llega(new_york, buenos_aires, 11).

%% Aviones y sus autonomías.

% autonomia(?avion, ?horas)
autonomia(boeing_767, 15).
autonomia(airbus_a320, 9).
autonomia(boeing_747, 10).


aerolinea(rio,[airbus_a320]).
aerolinea(buenos_aires, [airbus_a320, boeing_767]).
aerolinea(cordoba, [airbus_a320]).
aerolinea(atlanta, [boeing_747]).

%[(rio,[airbus_a320]), (buenos_aires, [airbus_a320, boeing_767]),
%(cordoba, [airbus_a320]), (atlanta, [boeing_747])].


%% Predicados pedidos:
%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% ciudades(-Ciudades)
ciudades(C) :- setof(X,Y^Z^llega(X,Y,Z),C).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% viajeDesde(+Origen,?Destino,-Recorrido,-Tiempo) -- Devuelve infinitos resultados.
viajeDesde(O,D,R,T) :- nums(0,T), llegoHasta(O,D,R,T).

llegoHasta(O,O,[O],0).
llegoHasta(O,D,R,T) :- numsUntil(0,T,Z), llega(O,Q,Z), ZN is T-Z, llegoHasta(Q,D,Re,ZN), append([O],Re,R).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% viajeSinCiclos(+Origen,?Destino,-Recorrido,-Tiempo)
viajeSinCiclos(O,D,R,T) :- ciudades(C), sacarPrimera(O,C,Cremaining), llegoHastaSinRep(O,D,R,T,Cremaining).

llegoHastaSinRep(O,O,[O],0,_).
llegoHastaSinRep(O,D,R,T,CR) :- length(CR,X), X>0, llega(O,Q,Z), member(Q,CR), sacarPrimera(Q,CR,CRR), llegoHastaSinRep(Q,D,Re,ZN,CRR), T is Z+ZN, append([O],Re,R).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% viajeMasCorto(+Origen,+Destino,-Recorrido,-Tiempo)
viajeMasCorto(O,D,R,T) :- viajeMasCortoAux(O,D,R,T,0).

viajeMasCortoAux(O,O,[O],0, _).
viajeMasCortoAux(O,D,R,T,C) :- (llegoHasta(O,D, _,C) ->	T is C, llegoHasta(O,D,R,T);	 CN is C+1, viajeMasCortoAux(O,D,R,T,CN)).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% grafoCorrecto
grafoCorrecto :- ciudades(X), grafoAux(X).

% Funci'on auxiliar de grafoCorrecto
grafoAux([]).
grafoAux([C|XS]) :- ciudades(P), todoAlcanzable(C,P,[C]), grafoAux(XS).

% Para cada ciudad, expando su vecindario hasta alcanzar el m'aximo, si alcanza, alcanza, sino perd'i.
todoAlcanzable(_,[],T) :- ciudades(X), length(X,L), length(T,L).
todoAlcanzable(O,[_|CSS],N) :- setof(Y, member(X,N)^Z^llega(X,Y,Z),NN), append(N,NN,NS), remove_dups(NS,NPUT), todoAlcanzable(O,CSS,NPUT).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% cubreDistancia(+Recorrido, ?Avion)
% Cabe aclarar que no tiene sentido preguntar con un recorrido de menos de dos ciudades
cubreDistancia([], _).
cubreDistancia([_], _).
cubreDistancia([X,Y|L],Av) :- llega(X,Y,T), autonomia(Av,Aut), T=<Aut, cubreDistancia([Y|L],Av).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%      INICIO EJERCICIO %%%%%%%%%%%%%%%%%%%%%%%% 
% vueloSinTransbordo(+Aerolinea, +Ciudad1, +Ciudad2, ?Tiempo, ?Avion)
% forma de uso: vueloSinTransbordo([(rio,[airbus_a320]), (buenos_aires, [airbus_a320, boeing_767]),(cordoba, [airbus_a320]), (atlanta, [boeing_747])], mdq, buenos_aires,T,Av).
% se asume que no est'a 2 veces en la lista la misma ciudad
vueloSinTransbordo([(C,_)|AA],C2,D,T,Av) :- C \= C2, vueloSinTransbordo(AA,C2,D,T,Av).
vueloSinTransbordo([(C,AVs)|_],C,D,T,A) :- member(A,AVs), setof(Ti, R^(viajeSinCiclos(C, D, R, Ti), cubreDistancia(R, A)), Ts), length(Ts, Tlenght), Tlenght>0, minl(Ts, T).
%%%%%%%%%%%       FIN EJERCICIO  %%%%%%%%%%%%%%%%%%%%%%%% 

%% Descomentar si se usa un archivo separado para las pruebas.
% ?- [pruebas].


%%%%%%%%%%%      INICIO AUXILIARES %%%%%%%%%%%%%%%%%%%%%%% 
%% AUXILIOOOOO, funciones de AUXILIOOO.
% nums(+X, -Y).
nums(X,X).
nums(X,Y) :- N is X + 1, nums(N,Y).

% numsUntil(+X, +Y, -Z)
numsUntil(X,Y,X) :- X =< Y.
numsUntil(X,Y,Z) :- X < Y, N is X+1, numsUntil(N,Y,Z).

sacarPrimera(_,[],[]).
sacarPrimera(X,[X|L],L).
sacarPrimera(X,[Y|L],[Y|L2]):- X \= Y, sacarPrimera(X,L,L2).

% remove_dups(+L, -NL):
remove_dups([],[]).
remove_dups([F | R],NR) :- member(F,R), remove_dups(R,NR).
remove_dups([F | R], [F | NR]) :- not(member(F,R)), remove_dups(R,NR).

% minl(List, Minimum).
minl([Only], Only).
minl([Head|Tail], Minimum) :- minl(Tail, TailMin), Minimum is min(Head, TailMin).
%%%%%%%%%%%       FIN AUXILIARES %%%%%%%%%%%%%%%%%%%%%%% 

